home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6940 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  5.1 KB
  1. Path: mail2news.demon.co.uk!ns.unibol.com
  2. From: John Girvin <jgirvin@bfs.unibol.com>
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: Collision Detects !!!!
  5. Date: Fri, 5 Apr 1996 16:01:03 GMT
  6. Message-ID: <199604051601.QAA18722@mailhost.unibol.com>
  7. X-NNTP-Posting-Host: ns.unibol.com
  8. X-Newsreader: TIN [version 1.2 PL2]
  9. X-Mail2News-Path: ns.unibol.com
  10.  
  11. On Thu, 4 Apr 1996 11:52:56 GMT, breese@imada.ou.dk (Bjorn Reese) wrote:
  12. :>John Girvin (jgirvin@bfs.unibol.com) wrote:
  13. :>> px2 = player->x + player->width        // PreCalc player BRHC coords.
  14. :>> py2 = player->y + player->height
  15. :>>
  16. :>> for (i=1; i<num_bullets; i++)
  17. :>> {
  18. :>>     if ( (bullet[i]->x - px2) < (bullet[i]->width + player->width) &&
  19. :>>          (bullet[i]->y - py2) < (bullet[i]->height + player->height) )
  20.  
  21. :>I might be missing something, but it seems to me that this only works
  22. :>under the assumption that the bullets are to the right and above the
  23. :>player (ie. bullet[i]->x < player->x and similar for y.) 
  24.  
  25. No, Im just missing a decent code-recall system in my brain :)
  26. This code is plain wrong! My faulty memory made me switch the
  27. order of the subtraction *blush* It should read:
  28.  
  29. if ( (px2 - bullet[i]->x) < (bullet[i]->width + player->width) &&
  30.       ^^^   ^^^^^^^^^^^^
  31.        swapped!
  32.      (py2 - bullet[i]->y) < (bullet[i]->height + player->height) )
  33.       ^^^   ^^^^^^^^^^^^
  34.        swapped!
  35.  
  36. Remember that these are *UNSIGNED* comparisons, thats the "trick".
  37.  
  38. Time for a few diagrams; Ill just do the X comparisons since Y is
  39. essentially the same. "P" is the player and "B" is the bullet:
  40.  
  41. 1) Bullet too far left:
  42.           +-----+
  43.           |     |
  44.           |  P  |
  45.           |     |
  46.           +-----+<-px2
  47.  
  48.      |<-------->| (this distance is px2-bx)
  49.  
  50. bx-> +-+
  51.      |B|
  52.      +-+
  53.  
  54. Think of (px2-bx) as the x-distance between the corners of the bounding
  55. rectangles. If this distance is further than the combined widths, then
  56. the rectangles are too far apart.
  57.  
  58. 2) Collision!
  59.       +-----+
  60.       |     |
  61.       |  P  |
  62.       |     |
  63.       +-----+<-px2
  64.  
  65.      |<---->| (this distance is px2-bx [which is < pw+bw])
  66.  
  67. bx-> +-+
  68.      |B|
  69.      +-+
  70.  
  71. Imagine sliding the "B" rectangle in diagram 1 above to the right (the 
  72. bullet moves closer to the player).  px2-bx will become smaller since 
  73. bx is increasing. Eventually the distance from x=px2 to x=bx will become 
  74. small enough so that the rectangles will overlap and you have a collision.
  75.  
  76. 3) Bullet too far right:
  77.  
  78.       +-----+
  79.       |     |
  80.       |  P  |
  81.       |     |
  82.       +-----+<-px2
  83.  
  84.             |<->| (this distance is px2-bx)
  85.  
  86.            bx-> +-+
  87.                 |B|
  88.                 +-+
  89.  
  90. This is the tricky one :) Here, bx>px2 (bx is further to the right than
  91. px2) so (px2-bx) is less than 0, right?
  92. Wrong! 
  93.  
  94. We are using *unsigned* arithmetic so (px2-bx) is actually a Very Big 
  95. Number, eg: -8 = 0xfff8 > 65000 , so the expression 
  96.      (px2 - bullet[i]->x) < (bullet[i]->width + player->width)
  97. is false and the check terminates.
  98.  
  99. :>as player->width is present on both sides of the inequality it can be
  100. :>omitted.
  101. Well spotted! I never noticed that myself :) I dont think it would make
  102. a big difference if bullet->width and bullet->height were constants. Youd
  103. save 2 adds outside the loop and have different constants inside.
  104.  
  105. :>The simple "check all ordered pair of entities" approach will
  106. :>always win over more sophisticated approaches if the number of
  107. :>entities are small (without specifying how small "small" is.)
  108.  
  109. Yes, I discovered this while experimenting to find the "best"
  110. collision detection method for my purposes! But it always comes
  111. down to comparing two entities, so if you optimize that check
  112. you always gain no matter how complex the scheme built on top.
  113. (c) Obvious Statements Inc. ;)
  114.  
  115. [static subsection collision checking]
  116. :>I never really liked this idea of subsections for two reasons.
  117. :>  (1) Problems with boundaries. To solve this you have to check
  118. :>      the neighbouring subsections as well.
  119. Not necessarily, I think. I read one document that claimed to solve
  120. this problem by shifting the sector dividing lines by half a sector
  121. width&height and repeating the collision check 4 times in all for
  122. :x,y x+0.5,y x,y+0.5 x+0.5,y+0.5. It was something like that anyway,
  123. but dont quote me - youve seen what my memory is like already ;)
  124.  
  125. I have the paper at home. Mail me at girv@girvnet.demon.co.uk if you 
  126. (or anyone else!) want it, or actual in-use 68k code to demonstrate 
  127. the 2-comparison collision check.
  128.  
  129. :>Subsections (static partitioning) can be sketched by this
  130. :>  for previous, current & next y-subsection
  131. :>    for previous, current & next x-subsection
  132. :>      CheckCollision
  133. 9 * CheckCollision for every sector = 0.5fps if youre lucky ;)
  134. The paper I was on about does 4 per sector I think. Much better!
  135.  
  136. cya, and sorry for any confusion!
  137. /John.
  138. __________________________________________________________________________
  139. |/\John Girvin : developing software for Unibol Inc., speaking for myself|
  140. |\/jgirvin@bfs.unibol.com | Amiga,!PC,net,Trek,SF,MTB,C2H50H,house,techno|
  141. |girv@girvnet.demon.co.uk | Youll never take me alive, Macro$loth fiends!|
  142. \A1200/030-40/10M/3.0 A500/000-7/2M/2.04 464/Z80-4/0.0625M/1.0 Team AMIGA/
  143.